/**
 * @Author：ming
 * @Date：2023/10/4 4:48 AM
 * @Filename：Lc210
 */

import java.util.ArrayList;
import java.util.HashSet;

/**
 * @author ming
 */
public class Lc210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        int len = prerequisites.length;
        if(len==0){
            return null;
        }
        HashSet<Integer> inset = new HashSet<>();
        HashSet<Integer> outset = new HashSet<>();
        ArrayList<int[]> list = new ArrayList<>();
        ArrayList<Integer> target = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            list.add(prerequisites[i]);
            int in = prerequisites[i][0];
            inset.add(in);
            int out = prerequisites[i][1];
            outset.add(out);
        }
        //找无入度的顶点
        int start =0 ;
        for (Integer out : outset) {
            if(!inset.contains(out)){
                start = out;
                break;
            }
        }


        //找齐拓扑排序
        int count =1;
        target.add(start);
        while (count<numCourses){
            for (int[] a : list) {
                if(a[1]==start){
                    target.add(a[0]);
                    start = a[0];
                    count ++;
                    break;
                }
            }
        }



        int[] a = new int[target.size()];
        for (int i = 0; i < target.size(); i++) {
            a[i] = target.get(i);
        }
        return a;


    }
}
